Skip to main content

Chapter 6. B-Tree Variants

Copy-on-Write​

It's an technique that consist of, whenever writing stuff, never mutating the input. Usually, we would copy and update it. When copy-on-write is used for B-Trees, we would copy the entirety of the B-Tree and just keep references for those unaltered. Databases like LMDB, one of the fastest K-V stores, uses for it's storage engine. It is much less complex than usual approach since it doesn't need synchronization between buffers.

Lazy B-Trees (WiredTiger/MongoDB)​

This concept consists of lazily writing page changes, buffering updates before flushing them to disk pages. Reads go through this Update Buffer and whenever we flushing times kicks in, we just merge both update buffer with the in-memory cached data. This buffering is handled by a different thread, not competing with read/write threads/operations.

Lazy Adaptative B-Tree​

This approach does the same Lazy B-Tree but to a group of nodes, named subtree. Buffering updates to this subtrees and applying only on those.

  • How does read operations happen in LA B-Trees? Seems to be expensive per BW-Tree.

Flash-Disk Tree ( FD-Tree)​

I honestly didn't grasp much about this Tree variant.

BW Tree (Buzzword Tree)​

Buzzword Tree make up for in-place updates by pre-prending Delta Nodes (changes like insert, etc) to the Base Nodes - using a LinkedList structure to link those nodes. The Base Node being the last node from the chain. Nodes are now logical entities. During read, now we need to traverse the entire node LinkedList to construct the node final-state.

This is somewhat similar to what LA-Trees do (see “Lazy-Adaptive Tree”): keeping updates separate from the main structure and replaying them on read.

Petrov, Alex. Database Internals (p. 192). O'Reilly Media. Edição do Kindle.

Examples of BWTrees

Cache Oblivious B-Tree​

  • Not being used in production by any database
  • No implementation outside of academic Creates a Two Level Memory model for all storage - enabling for platform specific configurations but creating something more general.

Take Away Points:

  • B-Trees are not perfect and have a lot of downsides
  • Wired Tigers uses Lazy B-Trees

Further reads